package org.demo.algorithm.lagou.column.relearn;

import org.demo.algorithm.common.ListNode;

/**
 * 链表反转
 * 方法一：
 * 使用栈，时间：O(n)、空间O(step)
 * 方法二：
 * 先整体反转，然后每隔step个元素移动到尾部，时间：O(2n)
 * 方法三：
 * 普通循环，需要构建prev、curr、next、last四个变量，时间：O(n)
 */
public class LinkedIntervalReversal {

    public static void reversal(ListNode head, int step) {
        if (null == head) {
            return;
        }
        ListNode last;
        ListNode prev = null;
        ListNode curr = head;
        ListNode next;
        int i = 0;
        while (curr != null) {
            next = curr.next;
            if (i % step == 0) {
                last = prev;
                curr.next = last;
            } else {
                curr.next = prev;
            }
            prev = curr;
            curr = next;
            i++;
        }
    }

}
